package searchInsertPosition;



public class Solution {
    public int searchInsert(int[] nums, int target) {
    	int left=0,right=nums.length-1;
    	int mid;
    	while (right-left>1){
    		mid = (left < 0 && right > 0) ? (left + right) / 2 : left + (right - left) / 2;
    		
    		if (mid==0) return mid;
    		if (mid==nums.length-1) return mid;
    		if ((nums[mid-1]<target) && (target<=nums[mid])) return mid;
    		if (target>=nums[mid]) left=mid;
    		if (target<nums[mid]) right=mid;
    	}
    	if (target<=nums[left]) return left;
    	if ((nums[left]<target) && (nums[right]<=right)) return right;
    	return right+1;

    }
	public static void main(String args[]){
		Solution so=new Solution();
		int[] nums={1,3};
		System.out.println(so.searchInsert(nums,2));
	} 
}